from .base import Sort
from .insertion import Insertion
from random import randint


class Quick(Insertion):
    '''三向切分快速排序'''

    def __init__(self, lt=True):
        Insertion.__init__(self, lt)
        self.LIMIT = 16

    def name(self):
        return "三向切分快速排序"

    def sort(self, data, low=0, hight=None):
        hight = len(data) if hight is None else hight
        if low >= hight:
            return
        if hight - low < self.LIMIT:
            Insertion.sort(self, data, low, hight)
        else:
            random_index = randint(low, hight-1)
            self.exchange(data, low, random_index)
            p = low+1
            i = low+1
            j = hight-1
            value = data[low]
            while i <= j:
                if self.compare(data[i], value):
                    i = i+1
                elif data[i] == value:
                    if i > p:
                        self.exchange(data, i, p)
                    p += 1
                    i += 1
                else:
                    self.exchange(data, i, j)
                    j -= 1
            eq = i-p
            switch_counter = min(p-low, eq)
            for k in range(0, switch_counter):
                self.exchange(data, low+k, i-k-1)
            lt = i-(p-low)
            self.sort(data, low, lt)
            self.sort(data, i, hight)
